package com.example.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 你被给定一个 m × n 的二维网格，网格中有以下三种可能的初始化值：
 * -1 表示墙或是障碍物
 * 0 表示一扇门
 * INF 无限表示一个空的房间。
 * 然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。
 * 你要给每个空房间位上填上该房间到 最近 门的距离，如果无法到达门，则填 INF 即可。
 *
 * 示例:
 * 输入
 * INF  -1  0  INF
 * INF INF INF  -1
 * INF  -1 INF  -1
 *   0  -1 INF INF
 *
 * 计算后应该是
 *   3  -1   0   1
 *   2   2   1  -1
 *   1  -1   2  -1
 *   0  -1   3   4
 *
 */
public class Leetcode286_WallsAndGates {
    public static void main(String[] args) {
        int room = Integer.MAX_VALUE;
//        int[][] rooms = {
//                {room, -1,   0,    room},
//                {room, room, room, -1  },
//                {room, -1,   room, -1  },
//                {0   , -1,   room, room}};

        int[][] rooms = {
                {room, -1,   -1,    room},
                {room, -1, room, -1  },
                {room, -1,   -1, -1  },
                {0   , -1,   room, room}};

        new Solution().wallsAndGates(rooms);

        for (int[] col : rooms) {
            for (int e : col) {
                System.out.print(e + ", ");
            }
            System.out.println();
        }

    }
    static class Solution {

        int room = Integer.MAX_VALUE;
        private int[][] directs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};// 定义上下左右四个方向

        /**
         * 解法一:BFS
         *
         * 多源BFS，反向从门开始考虑，即计算0与INF的最短距离。
         * 首先将所有0入队，然后开始出队，访问到INF后入队，并将其值更新为前一个节点的值+1
         * BFS搜索保证了每个位置只需要遍历到一次，第一次搜索到时一定是最短距离
         *
         * @param rooms
         */
        public void wallsAndGates(int[][] rooms) {
            if (rooms == null || rooms.length == 0 || rooms[0].length == 0)
                return;
            int rows = rooms.length;
            int columns = rooms[0].length;
            Queue<int[]> queue = new LinkedList<>();
            // 将所有的"门"的坐标入队
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (rooms[i][j] == 0) {
                        queue.add(new int[] {i, j});
                    }
                }
            }

            // 开始BFS遍历
            while (!queue.isEmpty()) {
                int[] point = queue.poll();
                for (int[] direct : directs) {// 四个方向查看并更新距离门的最近距离
                    int newX = point[0] + direct[0];
                    int newY = point[1] + direct[1];
                    if (newX < 0 || newX >= rows || newY < 0 || newY >= columns ||
                            rooms[newX][newY] != room) // 坐标越界或者不是房间时跳过
                        continue;
                    // 是房间则更新到门的距离
                    rooms[newX][newY] = rooms[point[0]][point[1]] + 1;
                    queue.add(new int[] {newX, newY});

                }
            }


        }
    }
}
